package com.LeeCode;

import java.util.*;

/**
 * 删除无效的括号
 */

public class Code301 {
    public static void main(String[] args) {
        String s = "()())()";
        System.out.println(new Code301().removeInvalidParentheses(s));
    }

    public List<String> removeInvalidParentheses1(String s) {
        List<String> ans = new ArrayList<>();
        Set<String> visited = new HashSet<>();
        Deque<String> queue = new LinkedList<>();

        // 初始化队列
        queue.offer(s);
        visited.add(s);

        boolean found = false; // 标记是否已找到有效字符串

        while (!queue.isEmpty()) {
            String current = queue.poll();

            // 如果当前字符串有效，加入结果，并不再往下删（保证最小删除）
            if (isValid(current)) {
                ans.add(current);
                found = true;
            }

            // 如果已经找到最优解，不再处理更深的层（即不再删除更多字符）
            if (found) {
                continue;
            }

            // 否则，尝试删除每一个字符，生成新字符串
            for (int i = 0; i < current.length(); i++) {
                // 跳过非括号字符？可选优化，但保留也可以
                if (current.charAt(i) != '(' && current.charAt(i) != ')') {
                    continue;
                }

                String next = current.substring(0, i) + current.substring(i + 1);

                if (!visited.contains(next)) {
                    queue.offer(next);
                    visited.add(next);
                }
            }
        }

        return ans;
    }

    // 判断括号是否有效
    private boolean isValid(String s) {
        int count = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                count++;
            } else if (c == ')') {
                count--;
                if (count < 0) {
                    return false; // 右括号多于左括号
                }
            }
        }
        return count == 0;
    }


    Set<String> result = new HashSet<>();

    public List<String> removeInvalidParentheses(String s) {
        int rmLeft = 0, rmRight = 0;

        // 计算最少需要删除几个右括号和左括号
        for (char c : s.toCharArray()) {
            if (c == '(') {
                rmLeft++;
            } else if (c == ')') {
                if (rmLeft == 0) {
                    rmRight++; // 多余的右括号
                } else {
                    rmLeft--; // 匹配掉一个左括号
                }
            }
        }

        backtrack(s, 0, 0, rmLeft, rmRight, "");
        return new ArrayList<>(result);
    }

    private void backtrack(String s, int index, int open, int rmLeft, int rmRight, String cur) {
        if (index == s.length()) {
            if (open == 0 && rmLeft == 0 && rmRight == 0) {
                result.add(cur);
            }
            return;
        }

        char c = s.charAt(index);

        if (c == '(' && rmLeft > 0) {
            backtrack(s, index + 1, open, rmLeft - 1, rmRight, cur); // 删除 (
        } else if (c == ')' && rmRight > 0) {
            backtrack(s, index + 1, open, rmLeft, rmRight - 1, cur); // 删除 )
        }

        // 不删除当前字符
        if (c == '(') {
            backtrack(s, index + 1, open + 1, rmLeft, rmRight, cur + c);
        } else if (c == ')') {
            if (open > 0) { // 只有前面有左括号才能加右括号
                backtrack(s, index + 1, open - 1, rmLeft, rmRight, cur + c);
            }
        } else {
            backtrack(s, index + 1, open, rmLeft, rmRight, cur + c); // 字母直接加
        }
    }
}
